A data "structure" refers to related data stored in a computer memory location. To enhance operating efficiency, a data structure may be "shared" by a plurality of processors which require the same information to perform various tasks. Synchronizing access to a shared data structure is a great challenge in designing software for computers with multiple processors, and is especially important whenever multiple processors attempt to update information in a data structure. Indeed, without efficient synchronization, the performance of a system including a shared data structure is severely degraded. This is because when one processor performs a data structure update, it is common for the entire data structure to be inaccessible (or "locked") to other processors. In other words, the non-updating processors must wait until the data structure is "unlocked" before the information contained in the structure can be accessed or updated. Another significant problem affecting the performance of a multiprocessor environment with shared resources is the inability of multiple processors to simultaneously perform updates on discrete data structure events without blocking each other.
The lack of synchronization in multiprocessor environments also contributes to the loss of first-in, first-out (hereinafter, FIFO) behavior during data structure updates resulting in the data structure being left in an "inconsistent" state. For example, assume a first processor begins modification of a data structure while a second processor waits to modify the structure. During an interval in which the first processor is in the process of unlocking the data structure, a third processor seizes the structure and performs its own information update. As a result, the third processor's updates are performed prior to the second processor's updates and the FIFO behavior of the data structure modification is destroyed. As is well-established, the loss of FIFO behavior during data structure modification results in significant performance degradation of multiprocessor systems.
Therefore, there is a need for an efficient, non-blocking operation for updating shared data structures in a multiprocessor environment.